As is well known in the art, content addressable memories (CAMs) can store a number of values, each of which may represent one entry. Stored entries may then be compared to an applied comparand value to generate a match indication. The relatively rapid speed at which CAMs can compare multiple entries to an applied comparand value has resulted in CAMs enjoying widespread use in various applications, such as packet processing, as but one example.
Conventional CAMs may include binary CAMs and ternary CAMs. Binary CAMs typically include entries that can each store a data value having a number of data bits. In most cases, a match indication can be generated when all bits of a comparand value match all the bits of an entry. CAMs may also include ternary CAMs. Ternary CAMs may typically include entries having data bits, some or all of which may be masked from a compare operation.
A conventional ternary CAM array will now be briefly described. Referring now to FIG. 9, a portion of a conventional ternary CAM array is set forth in a block diagram and designated by the general reference character 900. A conventional ternary array 900 may include a number of CAM cells 902(m,n), where m can indicate a particular array row position, and n can indicate a particular array column position. Each CAM cell 902(m,n) can be connected to one or more compare lines and a match line. In the example of FIG. 9, CAM cells 902(m,n) of the same column can be connected to the same complementary compare lines 904-m. Each pair of complementary compare lines 904-m may carry a comparand value that can be compared to a data value stored within a CAM cell 902(m,n). CAM cells 902(m,n) of the same row may be connected to the same match line 906-m. In a typical arrangement, CAM cells 902(m,n) of the same row may store data bit values for one entry.
Referring now to FIG. 10, a conventional example of a ternary CAM cell is shown in a block diagram and designated by the general reference character 1000. A conventional ternary CAM cell 1000 may include a data store 1002 that may store a data bit value, a mask store 1004 that may store a mask value, and a compare circuit 1006. A compare circuit 1006 can receive a data value, mask value, and comparand value to perform a match operation. While data and mask stores may take various forms, typically some sort of flip-flop type circuit, such as a conventional static random access memory (SRAM) type cell can be used as a data and/or mask store. Similarly, a compare circuit may take a variety of forms, but usually includes an exclusive-OR (XOR) or exclusive-NOR (XNOR) type circuit.
One example of a compare circuit, such as that shown as 1006, is shown in a schematic diagram in FIG. 11. A compare circuit 1100 may be connected between a match line 1102 and a first potential, VSS. Parallel paths 1104-0 and 1104-1 may be formed between a first potential VSS and a compare node 1106. In addition, a mask circuit 1108 may be formed between the compare node 1106 and the match line 1102. A path 1104-0 may receive a compare value C and an inverse data value D_. Similarly, a path 1104-1 may receive an inverse compare value C_ and a data value D. Thus, when a compare value C does not match a data value D, the paths (1104-0 and 1104-1) may be enabled (i.e., have a low impedance), connecting (discharging) the compare node 1106 to the first potential VSS. In contrast, when a compare value C matches a data value D, the paths are disabled (i.e., have a high impedance), isolating compare node 1106 from the first potential VSS.
A mask circuit 1108 may receive a mask value M_. If a mask value is active (low in this case), a mask circuit 1108 may isolate a match line 1102 from a compare node 1106. Thus, regardless of whether a match exists between a compare value C and a data value D, a match line 1102 may remain isolated from the first potential VSS. Conversely, if a mask value is inactive (high in this case), a mask circuit 1108 may connect a match line 1102 to a compare node 1106. In such a configuration, a match line 1102 may be connected to or isolated from a first potential VSS according to a match/mis-match between a data value D and a compare value C.
In this way, ternary CAMs may provide maskable matching operations.
Various CAM applications can include a variety of matching operation types. At one end of the spectrum are “exact” match operations, such as those that may be provided by a CAM. However, other applications may include more complicated match operations. For example, in some cases it may be desirable to determine if a given comparand value, or portion thereof, falls within a given range.
Ternary CAMs may provide limited range matching by masking out consecutive least significant bits of an entry value. Such an approach may require multiple entries in the event a given matching range does not fall along a bit value boundary. As but one example, an entry 1111 XXXX (where X represents a masked bit) may be used to match a range from 255 (1111 1111) to 240 (1111 0000). However, multiple entries may be needed to match a different range, such as 255 to 246. Such multiple entries may consume too much of the available CAM entry space.
Alternative conventional approaches to providing range matches can include a processor-oriented approach. Such an approach may store upper and lower values of a range. Such values may be compared to a comparand value according to some sort of algorithm to thereby determine if a range match has occurred. Such an approach may take multiple processor cycles, thus consuming more time than a typical CAM match operation. Still further, a process and the associated memory for storing the algorithm can be a relatively expensive solution to providing range matching when compared to a single device solution that can be offered by a CAM device.
While various conventional approaches to range matching exist, there remains a need to improve the speed at which range matching can be performed. In addition, or alternatively, there is a need for a range matching solution that does not consume multiple entries, as in the case of conventional ternary CAM solutions.